package com.algorithms.techniques;

import java.util.LinkedHashMap;
import java.util.Map;

import org.junit.Test;

public class OptimalCoinSelect
{
	Map<Integer,Integer> coinMap= new LinkedHashMap<Integer,Integer>();
	int[] coinTypes = new int[]{25,10,5,1};
	public void findNextCoin(int n)
	{
		int coinType=chooseCoinType(n);
		if(coinType!=-1)
		{
			int count=n/coinType;
			 coinMap.put(coinType, count);
			 findNextCoin(n%coinType);
		}
	}
	
	private int chooseCoinType(int n)
	{
		for(int type1:coinTypes)
		{
			if(n/type1>0)
				return  type1;
		}
		return -1;
	}
	@Test
	public void testCoinSelect()
	{
		findNextCoin(1);
		for(int coinType :coinMap.keySet())
		{
			System.out.println(coinType + "=="+ coinMap.get(coinType));
		}
	}
}
